import java.util.Iterator;
import java.util.NoSuchElementException;

public class Deque<Item> implements Iterable<Item> {
	private class Node{
		Item item;
		Node prev;
		Node next;
	}
	private Node first = null; // fist = current head node
	private Node last = null; // last = current tail node
	private int Size = 0;
   public Deque()                           // construct an empty deque
   {
	   Size = 0;
	   first = last = null;
   }
   
   public boolean isEmpty()                 // is the deque empty?
   {
	   return (Size == 0);
   }
   
   public int size()                        // return the number of items on the deque
   {
	   return Size;
   }
   
   public void addFirst(Item item)          // insert the item at the front
   {
	   if(item == null)
		   throw new java.lang.NullPointerException();
	   
	   Node newNode = new Node();
	   newNode.item = item;
	   Size ++;
	    
	   if(Size==1)
	   {
		   first = last = newNode;
	   }
	   else
	   {
		   newNode.next = first;
		   newNode.prev = first.prev;
		   first.prev = newNode;
		   first = newNode;
	   }
   }
   
   public void addLast(Item item)           // insert the item at the end
   {
	   if(item == null)
		   throw new java.lang.NullPointerException();
	   
	   Node newNode = new Node();
	   newNode.item = item;
	   Size ++;
	    
	   if(Size==1)
	   {
		   first = last = newNode;
	   }
	   else
	   {
		   newNode.prev = last;
		   newNode.next = last.next;
		   last.next = newNode;
		   last = newNode;
	   } 
   }
   public Item removeFirst()                // delete and return the item at the front
   {
	   if(Size < 1 || first == null)
		   throw new java.util.NoSuchElementException();
	   Node tmp = first;
	   Size --;
	   if(Size == 0)
		   first = last = null;
	   else
	   {
		   first = first.next;
		   first.prev = null;
	   }
	   return tmp.item;
   }
   
   public Item removeLast()                 // delete and return the item at the end
   {
	   if(Size < 1 || last == null)
		   throw new java.util.NoSuchElementException();
	   Node tmp = last;
	   Size --;
	   if(Size ==0)
		   first = last = null;
	   else
	   {
		   last = last.prev;
		   last.next = null;
	   }
	   return tmp.item;
   }

   @Override
   public Iterator<Item> iterator() {
   	// TODO Auto-generated method stub
   	return new ListIterator();
   }
   
	private class ListIterator implements Iterator<Item>
	{
		private Node current = first;
	
		@Override
		public boolean hasNext() {
			return (current != null);
		}
		
		@Override
		public Item next() {
			if(current == null)
				throw new java.util.NoSuchElementException();
			Item item = current.item;
			current = current.next;
			return item;
		}
		
		@Override
		public void remove() {
			throw new java.lang.UnsupportedOperationException();				
		}
	}
   
	public static void main(String[] args)   // unit testing
	{
		Deque<Integer> queue;
		boolean errStatus;
		Iterator<Integer> iter;
		   
		StdOut.println("---------------Err test");
		errStatus = false;
		queue = new Deque<Integer>();
		try {
			queue.removeFirst();
		} catch (NoSuchElementException e) {
			errStatus = true;
		}
		if(!errStatus)
		{
			StdOut.println("new Deque-removeFirst failed");
			return;
		}
		
		errStatus = false;
		try {
			queue.removeLast();
		} catch (NoSuchElementException e) {
			errStatus = true;
		}
		if(!errStatus)
		{
			StdOut.println("new Deque-removeLast failed");
			return;
		}

		errStatus = false;
		queue = new Deque<Integer>();
		try {
			queue.addFirst(null);
		} catch (NullPointerException e) {
			errStatus = true;
		}
		if(!errStatus)
		{
			StdOut.println("addFirst null failed");
			return;
		}
		
		errStatus = false;
		try {
			queue.addLast(null);
		} catch (NullPointerException e) {
			errStatus = true;
		}
		if(!errStatus)
		{
			StdOut.println("addLast null failed");
			return;
		}
		
		queue = new Deque<Integer>();
		queue.addFirst(4);
		queue.removeFirst();
		
		errStatus = false;
		try {
			queue.removeFirst();
		} catch (NoSuchElementException e) {
			errStatus = true;
		}
		if(!errStatus)
		{
			StdOut.println("used Deque1-removeFirst failed");
			return;
		}

		errStatus = false;
		try {
			queue.removeLast();
		} catch (NoSuchElementException e) {
			errStatus = true;
		}
		if(!errStatus)
		{
			StdOut.println("used Deque1-removeLast failed");
			return;
		}
		
		queue = new Deque<Integer>();
		queue.addFirst(4);
		queue.removeLast();

		errStatus = false;
		try {
			queue.removeFirst();
		} catch (NoSuchElementException e) {
			errStatus = true;
		}
		if(!errStatus)
		{
			StdOut.println("used Deque2-removeFirst failed");
			return;
		}

		errStatus = false;
		try {
			queue.removeLast();
		} catch (NoSuchElementException e) {
			errStatus = true;
		}
		if(!errStatus)
		{
			StdOut.println("used Deque2-removeLast failed");
			return;
		}
		
		queue = new Deque<Integer>();
		queue.addLast(4);
		queue.removeFirst();

		errStatus = false;
		try {
			queue.removeFirst();
		} catch (NoSuchElementException e) {
			errStatus = true;
		}
		if(!errStatus)
		{
			StdOut.println("used Deque3-removeFirst failed");
			return;
		}

		errStatus = false;
		try {
			queue.removeLast();
		} catch (NoSuchElementException e) {
			errStatus = true;
		}
		if(!errStatus)
		{
			StdOut.println("used Deque3-removeLast failed");
			return;
		}
		
		queue = new Deque<Integer>();
		queue.addLast(4);
		queue.removeLast();

		errStatus = false;
		try {
			queue.removeFirst();
		} catch (NoSuchElementException e) {
			errStatus = true;
		}
		if(!errStatus)
		{
			StdOut.println("used Deque4-removeFirst failed");
			return;
		}

		errStatus = false;
		try {
			queue.removeLast();
		} catch (NoSuchElementException e) {
			errStatus = true;
		}
		if(!errStatus)
		{
			StdOut.println("used Deque4-removeLast failed");
			return;
		}

		
		queue = new Deque<Integer>();

		errStatus = false;
		try {
			queue.iterator().next();
		} catch (NoSuchElementException e) {
			errStatus = true;
		}
		if(!errStatus)
		{
			StdOut.println("new iterator next failed");
			return;
		}
		
		queue.addFirst(4);
		queue.addLast(5);
		queue.addFirst(6);
		queue.addLast(7);
		queue.addFirst(8);
		queue.addFirst(9);
		queue.addLast(10);
		queue.addLast(11);
		iter = queue.iterator();
		iter.next();
		iter.next();
		iter.next();
		iter.next();
		iter.next();
		iter.next();
		iter.next();
		iter.next();
		try {
			iter.next();
		} catch (NoSuchElementException e) {
			errStatus = true;
		}
		if(!errStatus)
		{
			StdOut.println("next to end and next failed");
			return;
		}
				
		
		
		StdOut.println("Err test passed");			

		StdOut.println("---------------Function test");   
		   //test 1: addfirst & removefirst(stack)
		queue = new Deque<Integer>();
		
		queue.addFirst((int)6);
		if(queue.removeFirst() !=6)
		{
			StdOut.println("Single Err");
			return;
		}
			
		queue.addFirst(4);
		queue.addFirst(5);
		if(	queue.removeFirst() !=5 ||
			queue.removeFirst() !=4)
		{
			StdOut.println("Multiple Err");
			return;
		}
		
		StdOut.println("test1 passed");
			
		
		   //test 2: addfirst & removelast(queue)
		queue = new Deque<Integer>();
		
		queue.addFirst((int)6);
		if(queue.removeLast() !=6)
		{
			StdOut.println("Single Err");
			return;
		}
			
		queue.addFirst(4);
		queue.addFirst(5);
		if(	queue.removeLast() !=4 ||
			queue.removeLast() !=5)
		{
			StdOut.println("Multiple Err");
			return;
		}
		
		StdOut.println("test2 passed");
		
		   //test 3: addlast & removefirst(queue)
		queue = new Deque<Integer>();
		
		queue.addLast((int)6);
		if(queue.removeFirst() !=6)
		{
			StdOut.println("Single Err");
		return;
		}
			
		queue.addLast(4);
		queue.addLast(5);
		if(	queue.removeFirst() !=4 ||
			queue.removeFirst() !=5)
		{
			StdOut.println("Multiple Err");
			return;
		}
		
		StdOut.println("test3 passed");
		
		   //test 4: addlast & removelast(stack)
		queue = new Deque<Integer>();
		
		queue.addLast((int)6);
		if(queue.removeLast() !=6)
		{
			StdOut.println("Single Err");
		return;
		}
			
		queue.addLast(4);
		queue.addLast(5);
		if(	queue.removeLast() !=5 ||
			queue.removeLast() !=4)
		{
			StdOut.println("Multiple Err");
			return;
		}
	
		StdOut.println("test4 passed");
		
		queue = new Deque<Integer>();
		queue.addFirst(5);
		queue.addLast(6);
		queue.addFirst(4);
		queue.addLast(7);
		queue.addLast(8);
		iter = queue.iterator();
		int i=4;
		while(iter.hasNext())
		{
			if(iter.next() != i)
			{
				StdOut.println("Iterator Err");
				return;
			}
			i++;
		}

		StdOut.println("Iterator test passed");
	}
}